class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
 
    int m = 0, n = 0;
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
    int memo[1007][1007];
    int solve(vector<vector<int> >& matrix) { // dfs?
        memset(memo, -1, sizeof(memo));
        m = matrix.size(), n = matrix[0].size();
        // dfs(matrix, 0, 0);
        int ret = 0;
        for(int i = 0; i < m; ++i) // 可以以任何位置为起点
        {
            for(int j = 0; j < n; ++j)
            {
                ret = max(ret, dfs(matrix, i, j));
            }
        }
        return ret;
    }
 
    int dfs(vector<vector<int>>& arr, int sr, int sc)
    {
        if(memo[sr][sc] != -1)
            return memo[sr][sc];
        int len = 1;
        // cout << sr << " " << sc << " " << arr[sr][sc] << " " << dfsLevel << endl;
        for(int i = 0; i < 4; ++i)
        {
            int x = sr + dx[i], y = sc + dy[i];
            if(x >= 0 && x < m && y >= 0 && y < n && arr[x][y] > arr[sr][sc]) // 严格递增
            {
                len = max(len, 1 + dfs(arr, x, y));
            }
        }
        memo[sr][sc] = len;
        return len;
    }
};